package com.study.lintcode.my.code_20;

/**********************************************************************   
 * &lt;p&gt;文件名：Example_14.java &lt;/p&gt;
 * &lt;p&gt;文件描述：(描述该文件做什么) 
 * @project_name：LintCode
 * @author zengshunyao
 * @create 2019/1/6 1:15 
 * @history
 * @department：政务事业部
 * Copyright ChengDu Funi Cloud Code Technology Development CO.,LTD 2014 
 *                    All Rights Reserved.
 */
public class Example_14 {
    /**
     * @param nums:   The integer array.
     * @param target: Target to find.
     * @return: The first position of target. Position starts from 0.
     */
    public int binarySearch(int[] nums, int target) {
        // write your code here
        int low = 0;
        int high = nums.length;
        while (low <= high) {
            int mid = (high - low) / 2 + low;
            if (nums[mid] == target) {
                while (mid - 1 >= 0 && nums[mid - 1] == target) {
                    mid--;
                }
                return mid;
            } else if (nums[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(new Example_14().binarySearch(new int[]{1, 2, 3, 3, 4, 5, 10}, 3));
    }
}
